#define DEBUG
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

const int maxn=500000, mods=998244353;

ll powx[maxn+1];

void makeHash(int n, char s[], ll a[]) {
    powx[0] = 1;
    for (int i=1; i<=n; i++) {
        powx[i] = powx[i-1]*27%mods;
        a[i] = (a[i-1]*27+s[i]-'a'+1)%mods;
    }
}

void count(int n, char s[], int cnt[][26]) {
    for (int i=1; i<=n; i++) {
        for (int j=0; j<26; j++) {
            cnt[i][j] = cnt[i-1][j];
        }
        cnt[i][s[i]-'a']++;
    }
}

int gcd(int a, int b) {
    for (int r=a%b; r; a=b, b=r, r=a%b);
    return b;
}

bool cmp(ll a[], int l1, int r1, int l2, int r2) {
    ll u=(a[r1]+mods-a[l1-1]*powx[r1-l1+1]%mods)%mods,
        v=(a[r2]+mods-a[l2-1]*powx[r2-l2+1]%mods)%mods;
    return u==v;
}

int solve(int l, int r, ll a[], int cnt[][26]) {
    int n=r-l+1, t=r-l+1;
    for (int i=0; i<26; i++) {
        if (cnt[r][i]>cnt[l-1][i]) {
            t = gcd(t, cnt[r][i]-cnt[l-1][i]);
        }
    }

    for (int i=1; i<=sqrt(t); i++) {
        if (t%i==0) {
            int len=n/(t/i);
            if (cmp(a, l, r-len, l+len, r)) {
                return len;
            }
        }
    }
    for (int i=sqrt(t); i>0; i--) {
        if (t%i==0) {
            int len=n/i;
            if (cmp(a, l, r-len, l+len, r)) {
                return len;
            }
        }
    }

    return n;
}

int read() {
    int ret=0;
    char c;
    for (c=getchar(); c<'0' || c>'9'; c=getchar());
    for (; c>='0' && c<='9'; c=getchar()) {
        ret = ret*10+c-'0';
    }
    return ret;
}

int main() {
#ifdef DEBUG
    freopen("src.in", "r", stdin);
    freopen("src.out", "w", stdout);
#endif

    static char s[maxn+2];
    static int cnt[maxn+1][26];
    static ll a[maxn+2];
    int n, m;
    scanf("%d %s %d", &n, s+1, &m);
    makeHash(n, s, a);
    count(n, s, cnt);

    for (int i=1; i<=m; i++) {
        int l=read(), r=read();
        printf("%d\n", solve(l, r, a, cnt));
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
